#include <malloc.h>
#include <assert.h>
#include <stdio.h>
#include "heap.h"
#include "util.h"

void  createHeap(int capacity){
    array = (int*)malloc(sizeof(int) * (capacity + 1));
    c = capacity;
}

void insertHeap(int data){
    assert(size+1 < c);
    array[size+1] = data;
    size++;
    shiftUp(size);
}

int getLength(){
    return size;
}

void freeHeap(){
    free(array);
    array = NULL;
}

/**
 * 上 函数
 * @param index 数组的
 */
static void shiftUp(int index){
    //如果父节点元素的值比 新插入的元素值小 直接交换位置
    while (index > 1 && array[index / 2] < array[index]){
        swap(&array[index/2],&array[index]);
        index /= 2;
    }
}

void travel(){
    while (!isEmpty()){
        printf("%d ",getMaxHeap());
    }
    printf("\n");
}

void printHeap(){
    printf("head size:%d\n",size);
    int i;
    for (i = 1; i <= size; i++) {
        printf("%d ",array[i]);
    }
    printf("\n");

}

int getMaxHeap(){
    assert(size > 0);
    int item = array[1];
    swap(&array[1],&array[size]);
    size--;
    shiftDown(1);
    return item;
}

static void shiftDown(int i){
    //如果有左孩子
    while (2 * i < size){
        int j = 2 * i;
        //找到左右孩子较大的值于之交换
        if (j+1 <= size && array[j+1] > array[j]){
            j += 1;
        }
        //如果大于左右孩子的值直接跳出循环
        if (array[i] > array[j]){
            break;
        }
        swap(&array[i],&array[j]);
        //更新当前需要下沉索引
        i = j;
    }
}

int isEmpty(){
    return  size == 0;
}